public class Day4 {


    public static void main(String[] args) {
        uniquePaths(3,3);
    }
    static int m,n;
    static int[][] memos;
    public static  int uniquePaths(int _m, int _n) {
        m=_m;n=_n;
        memos = new int[m+1][n+1];
        return dfs(m-1,n-1);
    }
    public static int dfs(int i,int j){
        //1.回复记忆
        if(memos[i][j] != 0 ) return memos[i][j];
        //2.递归出口
        if(i==j && i==0) {
            memos[i][j]=1;
            return 1;
        }
        //3.递归
        int x=0,y=0;
        //(i,j-1),(i-1,j)
        if(j-1>=0) {
            x = dfs(i,j-1);
            memos[i][j-1]=x;
        }
        if(i-1>=0) {
            y = dfs(i-1,j);
            memos[i-1][j]=y;
        }
        return x+y;
    }


    //记忆化搜索
    int[] memo;
    public int fib(int n) {
        memo = new int[31];
        return dfs(n);
    }
    public int dfs(int n) {
        if(memo[n]!=0) return memo[n];
        if(n==1 || n==0) {
            memo[n]=n;
            return memo[n];
        }
        memo[n]=dfs(n-1)+dfs(n-2);
        return memo[n];
    }
}
